package bin_tree.leetcode;


import java.util.LinkedList;
import java.util.Queue;

/**
 * @author shkstart
 * @create 2022-10-23-16:22
 */
public class IsCompleteTree {
    public boolean isCompleteTree(TreeNode root){
        if (root == null) {
            return true;
        }
//        层序遍历二叉树
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
//        引入标志位,用来区分当前遍历过程所处第一还是第二处
        boolean isSecondStep = false;
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
//            处于第一阶段
            if(!isSecondStep){
                if(cur.left!=null&&cur.right!=null){
//                    当前cur左右子树都存在
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                } else if (cur.left == null && cur.right != null) {
//                    此时有右树没有左树，错误例子
                    return false;
                }else if(cur.left!=null){
                    //此时只有左树，以为此时正处于cur.right!=null
//                    是我们遇到的第一个只有左树的节点
//                    切换状态
                    isSecondStep = true;
                    queue.offer(cur.left);
                }else{
//                    此时左右树都为空，cur 是第一个碰到的叶子节点
                    isSecondStep = true;
                }
            }else {
//                此时处于第二阶段
//                第二阶段中所有节点都不可能有子节点
//                有一个反例就返回false;
                if(cur.left!=null || cur.right!=null){
                    return false;
                }
            }

        }

//        遍历结束，没有找到反例
        return true;
    }
}
